题目分析

这题思路明显，但是并不简单，暴力法没有难度，但是无法通过所有样例，要寻找一种时间复杂度为O(n)的算法解题。

暴力法

暴力法可以根据题目中给出的公式进行直接求解，遍历所有的景点对，两层循环，时间复杂度为$O(n^2)$，空间复杂度为$O(1)$，在这里给出了一种更加Pythonic的写法，一行代码实现。

class Solution(object):
    def maxScoreSightseeingPair(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        return max([A[i] + A[j] + i - j for i in range(len(A)) for j in range(i + 1, len(A))])

动态规划

上面的暴力法虽然简单，容易想到，但是无法通过所有样例，因此我们需要降低时间复杂度，发现在比较中浪费了大量的计算资源，每一个点都需要比较n次，所以时间复杂度为$O(n^2)$，可不可以记录之前的状态，每个点比较一次呢？我们发现公式可以分为两个部分，一部分是A[i] + i，另一部分是A[j] - j，最终将两部分相加即可。可以推出状态转移方程。
$$\begin{case} F = max(F, P + A[i] - i) \ P = max(P, A[i] + i) \end{case}$$
F为最佳观光组合，P为选择当前第i个点时，在i之前的所有点的最优选择，即上面的第一部分，记录A[i] + [i]的最大值为P，然后遍历所有点一次即可。

class Solution(object):
    def maxScoreSightseeingPair(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        pre_val = A[0]
        res = 0
        for i in range(1, len(A)):
            res = max(res, pre_val + A[i] - i)
            pre_val = max(pre_val, A[i] + i)
        return res

刷题总结

思路简单的题目一般都会有更巧妙的解法，对于数学问题，可能利用数学公式推出巧妙解，这个难度太大，或者是利用单调栈进行求解，或者利用动态规划进行求解。数学问题一般描述简单，难度适中，适合面试考察，因此小伙伴们尤其要注意。